package cn.hy.today;

import java.util.List;
import java.util.Stack;

// 美丽塔 II
class Solution_2866 {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        long ans = 0;
        long[] prefix = new long[n];
        long[] suffix = new long[n];

        // 单调栈
        Stack<Integer> stack1 = new Stack<>();
        // 单调栈
        Stack<Integer> stack2 = new Stack<>();

        // 顺序遍历递增栈
        for (int i = 0; i < n; i++) {
            while (!stack1.isEmpty() && maxHeights.get(stack1.peek()) > maxHeights.get(i)) {
                stack1.pop();
            }
            // 如果为空
            if (stack1.isEmpty()) {
                // 每个位置都建最大高度的塔， 下标是从0开始的
                prefix[i] = (long) maxHeights.get(i) * (i + 1);
            } else {
                // 能贡献的和（i-j）的位置能耐建最大高度的塔
                prefix[i] = prefix[stack1.peek()] + (long) (i - stack1.peek()) * maxHeights.get(i);
            }
            stack1.push(i);
        }
        // 逆序遍历 也是 递增栈
        for (int i = n - 1; i >= 0; i--) {
            while (!stack2.isEmpty() && maxHeights.get(stack2.peek()) > maxHeights.get(i)) {
                stack2.pop();
            }
            if (stack2.isEmpty()) {
                suffix[i] = (long) maxHeights.get(i) * (n - i);
            } else {
                suffix[i] = suffix[stack2.peek()] + (long) (stack2.peek() - i) * maxHeights.get(i);
            }
            stack2.push(i);
            // 计算了2个高度 需要减去一个
            ans = Math.max(ans, prefix[i] + suffix[i] - maxHeights.get(i));
        }
        return ans;
    }
}